home *** CD-ROM | disk | FTP | other *** search
/ APDL Eductation Resources / APDL Eductation Resources.iso / programs / misc / seek / _seek / technical < prev    next >
Encoding:
Text File  |  1995-03-07  |  7.8 KB  |  245 lines
  1. This document contains some technical information about SEEK. Programmers
  2. who want to write their own programs to perform operations on the text, will
  3. find pertinent information here.
  4.  
  5. Memory Problems
  6. ===============
  7.  
  8. In order that this program be useable on 1Mb machines, I have set the
  9. WimpSlot parameter quite tight. I'm a little worried that some
  10. configurations might occasionally run out of memory. If you do encounter
  11. memory related errors like "Too many nested procedures" or "no room for
  12. procedure call", then edit the !Run file and increase the WimpSlot
  13. parameter.
  14.  
  15. The compression algorithm.
  16. ==========================
  17.  
  18. Firstly there is a file (WORDSORT) which contains all the words used in the
  19. entire set of text files, sorted into alphabetical order. It also contains
  20. the number of occurrences of each word.
  21.  
  22. You can read WORDSORT like:-
  23.  
  24.    file%=OPENIN("WORDSORT")
  25.    REPEAT
  26.      INPUT#file%,word$,count%
  27.      . . .
  28.    UNTIL EOF#file%
  29.  
  30. The compressed file contains a number of 16-bit tokens, which can be one of
  31. five types:-
  32.  
  33.    Punctuation mark (after word):
  34.                bits 0-1:  Word Type = 3 (special)
  35.                bits 2-7:  Marker = 0
  36.                bits 8-15: Punctuation Character in ASCII
  37.  
  38.    Punctuation mark (before word):
  39.                bits 0-1:  Word Type = 3 (special)
  40.                bits 2-7:  Marker = 1
  41.                bits 8-15: Punctuation Character in ASCII
  42.  
  43.    Verse mark:
  44.                bits 0-1:  Word Type = 3 (special)
  45.                bits 2-7:  Marker = 2
  46.                bits 8-15: Verse Number
  47.  
  48.    Chapter mark:
  49.                bits 0-1:  Word Type = 3 (special)
  50.                bits 2-7:  Marker = 3
  51.                bits 8-15: Chapter Number
  52.  
  53.    Word Token:
  54.                bits 0-1:  Word Type
  55.                             0 = lower case
  56.                             1 = Initial Capital
  57.                             2 = ALL UPPER CASE
  58.                bits 2-15: Word Number
  59.  
  60.  
  61. Whenever a new chapter starts, there will be a chapter token.
  62.  
  63. Whenever a new verse starts, there will be a verse token.
  64.  
  65. Any characters other than alphabetic characters and apostrophies are
  66. represented by punctuation tokens. There are two classes of punctuation
  67. tokens, punctuation that follows a word, e.g.
  68.             THIS,      THAT!    THESE.
  69. and punctuation that precedes a word, e.g.
  70.             "THIS      (THAT
  71.  
  72. The actual words of the text are represented by a 14-bit word number. The
  73. maximum word number is 16,384. E.g. word #1 is "a", word #2 is "aaron", word
  74. #3 is "aaron's". If the word appears with a leading capital letter, then the
  75. word type is set to 1. If all the letters in the word are upper case, then
  76. the word type is set to 2. Word type 3 is for non-word tokens.
  77.  
  78. The words are always separated by spaces. There is no token for space, since
  79. the program knows that there is always a space after a word. The position of
  80. the space is after all the type-0 punctuation and before any type-1
  81. punctuation. This means that when decoding the text, you need to look at the
  82. next token before you can decide if a space is required at the current
  83. position.
  84.  
  85.  
  86. Let's look at an example:
  87.  
  88.    They said unto him, Rabbi, (which is to say, being interpreted, Master,)
  89.    where dwellest thou?
  90.  
  91. This becomes
  92.    WORD CAPITALISED     They
  93.    WORD                 said
  94.    WORD                 unto
  95.    WORD                 him
  96.    PUNCTUATION AFTER    ,
  97.    WORD CAPITALISED     Rabbi
  98.    PUNCTUATION AFTER    ,
  99.    PUNCTUATION BEFORE   (
  100.    WORD                 which
  101.    WORD                 is
  102.    WORD                 to
  103.    WORD                 say
  104.    PUNCTUATION AFTER    ,
  105.    WORD                 being
  106.    WORD                 interpreted
  107.    PUNCTUATION AFTER    ,
  108.    WORD CAPITALISED     Master
  109.    PUNCTUATION AFTER    ,
  110.    PUNCTUATION AFTER    )
  111.    WORD                 where
  112.    WORD                 dwellest
  113.    WORD                 thou
  114.    PUNCTUATION AFTER    ?
  115.    VERSE MARK
  116.  
  117. So the text is compressed from the 94 bytes of plain text (plus a bit for
  118. he chapter & verse numbers) to 24 16-bit tokens, i.e. 48 bytes.
  119.  
  120.  
  121.  
  122. The main objective of this compression is to improve word search speed. This
  123. is achieved as follows:-
  124.  
  125. Suppose we want to find all verses containing both "Rabbi" and
  126. "interpreted". We proceed as follows:-
  127.  
  128.    Look up "rabbi" and "interpreted" in the word list. The word "rabbi"
  129.    occurs 8 times, and "interpreted" occurs 11 times. Choose the least
  130.    frequent word to be the primary search parameter, in this case "rabbi".
  131.    The word number of "rabbi" is 1409.
  132.  
  133.    Load each file in turn into memory, and scan it.
  134.  
  135.    Look at each 16-bit token. If the word type is not 3, and the word number
  136.    is 1409 then we have a match. It could be "rabbi", "Rabbi" or "RABBI"
  137.    depending on the word type.
  138.  
  139.    Keep track of the last chapter and verse tokens during this search.
  140.  
  141.    When we find a verse containing "rabbi", jump back to the start of the
  142.    verse, and scan the verse for word number 921 ("interpreted").
  143.  
  144.    Only decompress the text once all the search keys have been satisfied.
  145.  
  146. Suppose we want to find all verses containing both "archimedes" and
  147. "computer".
  148.  
  149.    Look up "archimedes" and "computer" in the word list. "archimedes" is not
  150.    in the word list at all. Therefore, the word "archimedes" can't be in the
  151.    text, so there's no point looking for it.
  152.  
  153.    Reply immediately: SEARCH COMPLETE - NO OCCURRENCES FOUND.
  154.  
  155.  
  156. Timing Considerations
  157. =====================
  158.  
  159. A 3-word search takes almost exactly the same time as a 1-word search that
  160. produces the same number of hits.
  161.  
  162. The more hits that are found, the longer it takes, because we decompress the
  163. verse when we have a hit, and update the progress window.
  164.  
  165. The primary search algorithm is written in ARM code, but everything else is
  166. written in BASIC.
  167.  
  168. In Mode-27, on an A5000, using an IDE hard disk, a scan of the whole Bible
  169. takes 21 seconds.
  170.  
  171. Each verse found adds 0.07 seconds.
  172.  
  173.  
  174. Memory Considerations
  175. =====================
  176.  
  177. I want it to be usable on a 1 Mb machine. In order to achieve this, I'm
  178. limiting the maximum number of output lines to 1000.
  179.  
  180. Each verse can occupy several lines. 1000 output lines might be about 400
  181. verses.
  182.  
  183.  
  184. Configuration File 
  185. ==================
  186.  
  187. With the data files, there is a file called "Config" this contains
  188. information about the special effects and the files to be searched.
  189.  
  190. Special Effects
  191. ===============
  192.  
  193. There must always be three special effects. Each effect is controlled by
  194. three lines of information, these lines contain:-
  195.  
  196.       The effect name - this will appear in the FORMAT window
  197.       The string which switches the effect ON
  198.       The string which switches the effect OFF
  199.  
  200. For example:-
  201.  
  202.       Impress Super
  203.       {script super}
  204.       {script}
  205.  
  206. This defines an effect called "Impress Super". When selected, verses will be
  207. saved like 
  208.       
  209.       {script super}Jn 3:16{script} God so loved. . .
  210.  
  211. If you load this into Impression, "Jn 3:16" will appear in superscript.
  212.  
  213. Files to be searched
  214. ====================
  215.  
  216. The book files are defined as follows:-
  217.  
  218. The order of the entries controls the order in which the files will be
  219. searched. So normally the entries will be in the order that the books occur
  220. in the Bible.
  221.  
  222. Each entry contains:
  223.      The abbreviation for the book (used for references)
  224.      The filename
  225.      The type of the book
  226.      The full name of the book
  227. separated by commas
  228.  
  229. Book types are used to control the range of the search. The types correspond
  230. to the icons in the selection window.
  231.      Type 1: Pentateuch       Genesis-Deuteronomy
  232.      Type 2: History          Joshua-Esther
  233.      Type 3: Poetry           Job-Song of Solomon
  234.      Type 4: Major Prophets   Isaiah-Daniel
  235.      Type 5: Minor Prophets   Hosea-Malachi
  236.      Type 6: Gospels          Matthew-John
  237.      Type 7: Acts             Acts
  238.      Type 8: Letters          Romans-Jude
  239.      Type 9: Revelation       Revelation
  240.  
  241. The program is very sensitive to errors in the config file, so save a copy
  242. first, and be careful with those commas.
  243.  
  244.  
  245.